COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00032 00003	\proclaim Lemma. For $x>0${}
C00034 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a12.tex[162,phy] \today\hfill}

\parskip 5pt
\bigskip
\line{\bf More Fresh Cookies\hfill}

\proclaim Lemma {\rm (eigenvector)}. Let $T$ be a linear transformation on
a vector space, $T(Y↓i)=\rho↓iY↓i$ for a set $\{Y↓i\}$ of eigenvectors.
If $T(X)=\alpha X+\sum↓i\beta↓iY↓i$, $\alpha≠\rho↓i$, then
$Z=X+\sum↓i{\beta↓iY↓i\over\alpha -\rho↓i}$ is an eigenvector;
$$T(Z)=\alpha X+\sum↓iY↓i\left(\beta↓i+{\beta↓i\rho↓i\over\alpha -\rho↓i}
\right)=\alpha Z\,.\quad\blackslug$$

\noindent {\bf The Conditional Expected Value Lemma.}
Let $X$ and $Y$ be discrete random variables with joint distribution
$p(x,y)$. Then $E\bigl(\phi(X,Y)\bigr)=\sum↓{x,y}\phi(x,y)p(x,y)$.
The marginal probabilities of $x$ and~$y$ are
$$\eqalign{f(x)&=\sum↓yp(x,y)\cr
\noalign{\smallskip}
g(y)&=\sum↓xp(x,y)\,.\cr}$$
If $\phi(x,y)=\phi(x)$ is a function of $x$ alone, 
$$E\bigl(\phi(X)\bigr)=\sum↓x\left(\phi(x)\sum↓yp(x,y)\right)=\sum↓x\phi(x)f(x)\,.$$
Similarly, $E\bigl(\phi(Y)\bigr)=\sum↓y\phi(y)g(y)$.
The expected value of $\phi(X,Y)$ conditioned on $Y=y$ is a function of~$y$,
$$E\bigl(\phi(X,Y)\mid Y=y\bigr)=\left.\biggl(\sum↓x\phi(x,y)p(x,y)\biggr)\right/
g(y)\,,$$
abbreviated $E(\phi\mid y)$. Then
$$\eqalign{E\bigl(E\bigl(\phi(X,Y)\mid Y=y\bigr)\bigr)&=
E\left.\left(\biggl(\sum↓x\phi(x,y)p(x,y)\biggr)\right/g(y)\right)\cr
\noalign{\smallskip}
&=\sum↓y\sum↓x\phi(x,y)p(x,y)=E\bigl(\phi(X,Y)\bigr)\,.\cr}$$

{\sl In abbreviated form}, $E\bigl(E(\phi\mid y)\bigr)=E(\phi)$. If
$E(\phi\mid y)$ is a polynomial in $y$, $\sum a↓iy↑i$, then
$E(\phi)=\sum a↓iM↓i(Y)$, where $M↓i$ is the $i$-th moment $E(y↑i)$,
and only the moments of~$Y$ need be known. If $E(\phi\mid y)$ is linear
in~$y$, $E(\phi)=E(\phi\mid\bar{y})$.

A paradigm for using the lemma is:
To evaluate $E\bigl(\phi(x,y)\bigr)$, successively find
$$\eqalign{g(y)&=\sum↓xp(x,y)\cr
\noalign{\smallskip}
\psi(y)&=\sum↓x\phi(x,y)p(x,y)\cr
\noalign{\smallskip}
E(\phi\mid y)&=\psi(y)/g(y)\cr
\noalign{\smallskip}
E(\phi)&=\sum↓yE(\phi\mid y)g(y)\,.\cr}$$
A similar result gives variance in terms of conditional variance:
$$V\bigl(\phi(X,Y)\bigr)=E\bigl(V\bigl(\phi(X,Y)\mid x\bigr)\bigr)+
V\bigl(E\bigl(\phi(X,Y)\mid x\bigr)\bigr)\,.$$

\proclaim Lemma {\rm (recurrence)}. Let $x↓t$ be defined by the recurrence
$x↓{t+1}=ax↓t+bt+c$, $a≠1$. One solution is linear in~$t$:
$x↓t={b\over 1-a}t+{c\over 1-a}-{b\over (1-a)↑2}$. For other
solutions, add any multiple of~$a↑t$ (the solution of $x↓{t+1}=ax↓t$)
to satisfy a boundary condition. If $x↓0=0$, the solution is
$x↓t={b\over 1-a}t+\left({c\over 1-a}-{b\over (1-a)↑2}\right)(1-a↑t)$.

In coalesced hashing  with table size~$H$, there is at any time a
multiset~$S$ of list lengths; initially $S=\emptyset$. At each step
of successful insertion, each $\sigma\in S$ has (disjoint) probability
$\sigma/H$ of being increased by one. If no~$\sigma$ is increased, 
a~new $\sigma =1$ is inserted onto~$S$. Define
$$\eqalign{S↓p&=\sum↓{\sigma\in S}\sigma↑p\cr
\noalign{\smallskip}
S↓{\bar{p}}&=\sum↓{\sigma\in S}\sigma↑{\bar{p}}\,,\cr}$$
which we will call the $p↑{\rm th}$ {\sl power sum\/} and {\sl factorial
power sum\/} of~$S$. Let $t$ be the number of insertions that have taken
place. At $t=0$, all $S↓p$ and~$S↓{\bar{p}}$ are zero, and for all~$t$,
$S↓1=S↓{\bar{1}}=t$. Whenever some nonzero~$\sigma$ is incremented, there are
collisions; the number of collisions is uniform from~1 to~$\sigma$, with
mean ${\sigma+1\over 2}$ and variance ${\sigma↑2-1\over 12}$. Let $r$
be the cumulative number of collisions. We want to compute the mean
and variance of~$r$ after $t$~steps.
First we compute $E(r\mid S)$ and $V(r\mid S)$, and then use the lemmas to derive
$E(r)$ and $V(r)$. Holding $S$ fixed, for each $\sigma\in S$ and
$1≤i≤\sigma -1$, let $r↓{\sigma i}$ be the number of collisions that
occurred when the list increased in size from~$i$ to $i+1$.
Then 
$$r=\sum↓{\scriptstyle\sigma\in S\atop\scriptstyle 1≤i≤\sigma -1}
r↓{\sigma i}\,,$$
{}
$$E(r\mid S)=
\sum↓{\scriptstyle\sigma\in S\atop\scriptstyle
1≤i≤\sigma-i}E(r↓{\sigma i})=
\sum↓{\scriptstyle\sigma\in S\atop\scriptstyle
1≤i≤\sigma-i}{i+1\over 2}
=\sum↓{\sigma}{\sigma↑{\bar{2}}-2\over 4}={1\over 4}(S↓{\bar{2}}-2S↓{\bar{0}})
\,.$$
Because all the $r↓{\sigma i}$ are independent,
$$\eqalign{V(r\mid S)&=
\sum↓{\scriptstyle\sigma\in S\atop\scriptstyle
1≤i≤\sigma-i}V(r↓{\sigma i}\mid S)
=
\sum↓{\scriptstyle\sigma\in S\atop\scriptstyle
1≤i≤\sigma-i}{i↑2-1\over 12}\cr
\noalign{\smallskip}
&={1\over 12}\sum↓{\scriptstyle \sigma\in S\atop 2≤i≤\sigma}i↑{\bar{2}}-3i↑{\bar{1}}
={1\over 12}\sum↓{\sigma}\left.\left({i↑{\bar{3}}\over
 3}-3{i↑{\bar{2}}\over 2}\right)\right|↓1↑{\sigma}
={1\over 72}\sum↓{\sigma}(2\sigma↑{\bar{3}}-9\sigma↑{\bar{2}}+6)\cr
\noalign{\smallskip}
&={1\over 72}(2S↓{\bar{3}}-9S↓{\bar{2}}+6S↓{\bar{0}})\,.\cr}$$
By the lemma, $E(r)=E\bigl(E(r\mid S)\bigr)
=E\bigl({1\over 4}(S↓{\bar{2}}-2S↓{\bar{0}})
\bigr)$. Now we need $E(S↓{\bar{p}})$ after $t$~insertions. Suppose we know
the actual value of~$S↓{\bar{p}}$ at time~$t$. Then the expected value
of~$S↓{\bar{p}}$
at time $t+1$ is 
$$\eqalign{E(S'↓{\bar{p}}\mid S)&=
S↓{\bar{p}}+{1\over H}\biggl(\sum↓{\sigma\in S}\sigma\bigl((
\sigma +1)↑{\bar{p}}-\sigma↑{\bar{p}}\bigr)+(H-t)1↑{\bar{p}}\biggr)\cr
\noalign{\smallskip}
&=S↓{\bar{p}}+{1\over H}\biggl(\sum↓{\sigma\in S}p\sigma↑{\bar{p}}+p!\,
(H-t)\biggr)\cr
\noalign{\smallskip}
&=S↓{\bar{p}}\left(1+{p\over H}\right)+p!\,\left(1-{t\over H}\right)\,,\cr}$$
so by the conditional expected value
lemma, the expected value  of~$S↓{\bar{p}}$
at time~$t$
is governed by the recurrence
$$x↓{t+1}=\left(1+{p\over H}\right)x↓t+p!\,\left(1-{t\over H}\right)\,.$$
For $p≠0$, by the recurrence lemma, since $x↓0=0$,
$$\displaylines{x↓t={-p!/H\over 1-\bigl(1+{p\over H}\bigr)}t+\left(
{p!\over -p/H}-{-p!/H\over (-p/H)↑2}\right)\left(1-\left(1+{p\over H}\right)↑t
\right)\,;\cr
\noalign{\smallskip}
E(S↓{\bar{p}})=H\,p!{p-1\over p↑2}\left(\left(1+{p\over H}\right)↑t-1\right)
+(p-1)!\,t\cr}$$
so
$$\eqalign{E(S↓{\bar{1}})&=1\quad\hbox{(obviously)}\cr
\noalign{\smallskip}
E(S↓{\bar{2}})&={H\over 2}\left(\left(1+{2\over H}\right)↑t-1\right)+t\cr}$$
For $p=0$,
$$E(S↓{\bar{0}})=\sum↓{0≤i≤t-1}\left(1-{i\over H}\right)=t\left(1-{t-1\over
2H}\right)\,.$$

Returning to $E(r)$ and $V(r)$,
$$\eqalign{E(r)&={1\over 4}E(S↓{\bar{2}}-2S↓{\bar{0}})\cr
\noalign{\smallskip}
&={1\over 4}\left({H\over 2}\left(\left(1+{2\over H}\right)↑t-1\right)
+t-2t\left(1-{t-1\over 2H}\right)\right)\cr
\noalign{\smallskip}
&={1\over 4}\left({H\over 2}\left(1+{2\over H}\right)↑t-{H\over 2}+t-2t+
{t(t-1)\over H}\right)\cr
\noalign{\smallskip}
&={H\over 8}\left(1+{2\over H}\right)↑t-{H\over 8}-{t\over 4}+{t↑2\over 4H}-
{t\over 4H}\,.\cr}$$
Defining the load factor $\alpha =t/H$,
$$\eqalign{E(r)&\approx H\left({1\over 8}\left(1+{2\over H}\right)↑t-{1\over 8}
-{\alpha\over 4}+{\alpha↑2\over 4}\right)-{\alpha\over 4}\cr
\noalign{\smallskip}
&\approx H\left({e↑{2\alpha}\over 8}-{1\over 8}-{\alpha\over 4}+{\alpha↑2\over 4}
\right)\,.\cr}$$
{}
$$\vcenter{\halign{\hfil$#$\qquad&$#$\hfil\cr
\alpha&E(r)\cr
\multispan2\hrulefill\cr
\ll 1&t(\alpha/2+O\bigl(\alpha↑2)\bigr)\cr
0.1&0.052t\cr
0.5&0.304t\cr
1.0&0.799t\cr}}$$
Even when the table is nearly full, there is an average of $0.8$ collisions
per unsuccessful search.

%a13 follows
\bigskip
$$V(r\mid S)={1\over 72}(2S↓{\bar{3}}-9S↓{\bar{2}}+6S↓{\bar{0}})$$

$$\eqalign{E\bigl(V(r\mid S)\bigr)
&={1\over 72}\bigl(2E(S↓{\bar{3}})-9E(S↓{\bar{2}})
+6E(S↓{\bar{0}})\bigr)\cr
\noalign{\smallskip}
&={1\over 27}H\left(1+{3\over H}\right)↑t-{1\over 27}H-{1\over 16}
H\left(1+{2\over H}\right)↑t+{1\over 16}H+{1\over 72}\left(t-{3t↑2\over H}
+{3t\over H}\right)\cr
\noalign{\smallskip}
&=H\left({1\over 27}\left(1+{3\over H}\right)↑t-{1\over 16}\left(1+{2\over H}
\right)↑t+{11\over 432}+{\alpha\over 72}-{\alpha↑2\over 24}\right)
+{\alpha\over 24}\cr
\noalign{\smallskip}
&\approx H\left({1\over 27}e↑{3\alpha}-{1\over 16}e↑{2\alpha}+{11\over 432}
+{\alpha\over 72}-{\alpha↑2\over 24}\right)\cr}$$
When $\alpha =1$, $E\bigl(V(r\mid S)\bigr)=0.28H$,
$$\eqalign{V\bigl(E(r\mid S)\bigr)&=V\left({1\over 4}(S↓{\bar{2}}-2S↓{\bar{0}}\right)\cr
\noalign{\smallskip}
&=E\left(\left({S↓{\bar{2}}-2S↓{\bar{0}}\over 4}\right)↑2\right)
-\left(E\left({S↓{\bar{2}}-2S↓{\bar{0}}\over 4}\right)\right)↑2\cr
\noalign{\smallskip}
&={1\over 16}E\bigl((S↓{\bar{2}}-2S↓{\bar{0}})↑2\bigr)-
\left({H\over 8}\left(1+{2\over H}\right)↑t-{H\over 8}-{t\over 4}
+{t↑2\over 4H}-{t\over 4H}\right)↑2\cr}$$
where the first term as yet eludes analysis.


\vfill\eject
%see next page (tossed on 9-30-86)
%\magnification\magstephalf
%\input macro.tex
%\def\today{\ifcase\month\or
%  January\or February\or March\or April\or May\or June\or
%  July\or August\or September\or October\or November\or December\fi
%  \space\number\day, \number\year}
%\baselineskip 14pt
%\rm
\line{\sevenrm a11.tex[162,phy] \today\hfill}

\bigskip
\line{\bf Mean and Variance of Cookie Monster Tail Size\hfill}

In coalesced hashing with table size~$h$, containing $t$~keys, let $c$
be a pointer to the first word of the cellar region. Initially,
$c=h+1$. There are $h+1-c$ cells in the cellar. The other $c-1$
cells include $h-t$ empty cells, randomly distributed. When another key
is inserted, there is probability $t/h$ of a collision. When a collision
occurs, $c$~is moved left to an empty cell, where the new key is inserted.
Let $i$ be the amount by which $c$ moves.

In what follows, we analyze the mean and variance of~$c$ after $t$~insertions.
Much of the analysis is only needed for the variance.

\proclaim Table Search Lemma. A table has size $s$, and contains $u$~unused
cells in random positions. Define $i$ as the index of the first empty cell.
That value has probability $\left.{s-i\choose u-1}\right/{s\choose u}$,
so 
$$E(i↑{\bar{p}})=p!\sum↓i{{i-p-1\choose p}{s-i\choose u-1}\over
{s\choose u}}=p!\,{{s+p\choose u+p}\over{s\choose u}}={p!(s+1)↑{\bar{p}}\over
(u+1)↑{\bar{p}}}\,.$$
In coalesced hashing, $s=c-1$, $u=h-t$, so
$$\eqalign{E(i\mid c)&={c\over h-t+1}\cr
\noalign{\smallskip}
E(i↑{\bar{2}}\mid c)&={2c↑{\bar{2}}\over (h-t+1)↑{\bar{2}}}\cr
\noalign{\smallskip}
E(i↑2\mid c)&={c(2c-h+t)\over (h-t+1)↑{\bar{2}}}\,.\cr}$$
$$\eqalign{E(i\mid c)&={c\over h-t+1}\,;\cr
\noalign{\smallskip}
E(i↑{\bar{2}}\mid c)&={2c↑{\bar{2}}\over (h-t+1)↑{\bar{2}}}\,;\cr
\noalign{\smallskip}
E(i↑2\mid c)&={c(2c-h+t)\over (h-t+1)↑{\bar{2}}}\,.\cr}$$

At the next insertion, $c$~is decreased, with probability $t/h$,
by~$i$, where the statistics of~$i$ are given above. Let $c'$ be the
new value of~$c$, after the $t+1↑{\rm st}$ insertion.
$$\eqalign{E(c'\mid c)&=c-{t\over h}E(i\mid c)=c{(h+1)(h-t)\over h(h-t+1)}\,;\cr
\noalign{\smallskip}
E(c')&=E\bigl(E(c'\mid c)\bigr)=E(c){(h+1)(h-t)\over h(h-t+1)}\,.\cr}$$
Letting $x↓t$ be $E(c)$ at time $t$,
$$\eqalignno{x↓0&=h+1\cr
x↓{j+1}&=x↓j{(h+1)(h-j)\over h(h-j+1)}\cr
\noalign{\hbox{therefore}}
E(c)&=\left({h+1\over h}\right)↑t(h-t+1)\,.\cr}$$
This solves Knuth's problem 6.4--41, rated [40], while just warming up.

Next we look at $E(c↑2)$, hoping to get $V(c)$; 
$$\eqalign{E(c'↑2\mid c)&=c↑2-{t\over h}\bigl(2c\,E(i)-E(i↑2)\bigr)\cr
\noalign{\smallskip}
&=c↑2-{t\over h}\left(2c\cdot {c\over h-t+1}-{c(2c-h+t)\over(h-t+1)↑{\bar{2}}}
\right)\cr
\noalign{\smallskip}
&=c↑2\left(1-{2t\over h(h-t+1)}+{2t\over h(h-t+1)↑{\bar{2}}}\right)-c
{t(h-t)\over h(h-t+1)↑{\bar{2}}}\cr
\noalign{\smallskip}
&=c↑2{(h+2)(h-t)\over h(h-t+2)}-c{t(h-t)\over h(h-t+1)↑{\bar{2}}}\cr}$$
to which we apply the eigenvalue lemma. The eigenvector, conveniently,
is~$c↑{\bar{2}}$.

Notice that I could have pulled a rabbit out of my hat by starting off with
$E(c↑{\bar{2}})$; I~have shown the false start, to show how a systematic
approach uncovers the solution.

So,
$$\eqalign{E(c↑{\bar{2}'}\mid c)&=c↑{\bar{2}}{(h+2)(h-t)\over h(h-t+2)}\cr
\noalign{\smallskip}
E(c↑{\bar{2}'})&=E(c↑{\bar{2}}){(h+2)(h-t)\over h(h-t+2)}\,.\cr}$$
Letting $x↓t=E(c↑{\bar{2}})$ after $t$~insertions,
$$\eqalign{x↓0&=(h+1)↑{\bar{2}}\cr
\noalign{\smallskip}
x↓{j+1}&=x↓j{(h+2)(h-j)\over h(h-j+2)}\,.\cr}$$
Forming the product of both sides for $0≤j≤t-1$, and cancelling~$x$'s,
$$\eqalign{x↓t&=x↓0\left({h+2\over h}\right)↑t
{h!/(h-t)!\over (h+2)!/(h+2-t)!}\cr
\noalign{\smallskip}
E(c↑{\bar{2}})&=\left({h+2\over h}\right)↑t(h-t+1)↑{\bar{2}}\cr
\noalign{\smallskip}
V(c)&=E(c↑{\bar{2}})-E(c)-E(c)↑2\cr
\noalign{\smallskip}
&=\left({h+2\over h}\right)↑t(h-t+1)↑{\bar{2}}-\left({h+1\over h}\right)↑t
(h-t+1)-\left({h+1\over h}\right)↑{2t}(h-t+1)↑2\cr}$$

Now some approximations:
Let $\alpha =t/h$, the load factor.
$$E(c)=\left({h+1\over h}\right)↑t(h-t+1)\approx t\,e↑{\alpha}\left(\,
{1\over \alpha}-1\right)\,.$$
Expected number of probes is
$$\eqalign{E(h+1-c)
&=h+1-\left({h+1\over h}\right)↑t(h-t+1)\approx t\left(\,{1\over\alpha}
-e↑{\alpha}\left(\,{1\over\alpha}-1\right)\right)\cr
\noalign{\smallskip}
&=t\left((e↑{\alpha}-1)\left(1-{1\over\alpha}\,\right)+1\right)=t\,f(\alpha)\cr}$$
{}
$$\vcenter{\halign{$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\quad%
&$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\cr
\alpha&\epsilon&0.1&0.2&0.4&0.5&0.6&0.8&1.0\cr
\noalign{\smallskip}
f(\alpha)&\epsilon/2&0.053&0.114&0.262&0.351&0.452&0.694&1.000\cr}}$$

Approximating $V(c)$ is rather delicate, so we need (what else?) another
lemma or two.

\proclaim Lemma. Approximating $(1+y)↑p$.
If $y>0$, $(1+y)↑p$ lies between successive terms in the sequence
$1,\exp(py),\exp\bigl(p(y-y↑2/2)\bigr),\exp\bigl(p(y-y↑2/2+y↑3/3)\bigr),\ldots,
\prod↓{1≤i≤n}\exp\bigl(-p(-y)↑i/i),\ldots\,$.

\noindent{\bf Proof.}
If $x>0$, 
$$\eqalign{%
&1-(1+x)\sum↓{1≤i≤n}(-x)↑{i-1}=(-x)↑n\,;\cr
\noalign{\smallskip}
&{1\over 1+x}-\sum↓{1≤i≤n}(-x)↑{i-1}={(-x)↑n\over 1+x}\,;\cr
\noalign{\smallskip}
&\int↓0↑y{dx\over 1+x}-\int↓0↑y\sum↓{1≤i≤n}(-x)↑{-i}\,dx
\hbox{has ${\rm sign}(-1)↑n$, for $x>0$.}\cr
\noalign{\smallskip}
&{\rm sign}\left(p\ln(1+y)-p\sum↓{1≤i≤n}-{(-y)↑i\over i}\right)=(-)↑n\,.\cr}$$
Because ${\rm sign}(u-v)={\rm sign}(e↑u-e↑v)$,
$${\rm sign}\left((1+y)↑p-\exp\left(p\left(y-{y↑2\over 2}+{y↑3\over 3}
-\cdots -{(-x)↑n\over n}\right)\right)\right)=(-)↑n\,.$$

\proclaim Lemma: Approximating $e↑{-x}$ by its Taylor Series.
For $x>0$, $e↑{-x}$ is between successive terms of its Taylor series
$1-x+x↑2/2-x↑3/6+\cdots\,$.

\noindent{\bf Proof.}
Let $f↓i(x)$ be an arbitrary function that is negative if $i$ is odd,
positive if $i$ is even. By inductive hypothesis
$e↑{-x}=\sum↓{0≤i≤n}{(-x)↑i\over i!}-f↓n(x)$, so
$$e↑{-y}=1-\int↓0↑ye↑{-x}\,dx=1+\sum↓{0≤i≤n}{(-y)↑{i+1}\over
(i+1)!}+\int↓0↑yf↓n(x)\,dx
=\sum↓{0≤i≤n+1}{(-y)↑i\over i!}-f↓{n+1}(x)\,.$$
%$$\eqalign{e↑{-y}&=1-\int↓0↑ye↑{-x}\,dx&=1+\sum↓{0≤i≤n}{(-y)↑{i+1}\over
%(i+1)!}+\int↓0↑yf↓n(x)\,dx\cr
%\noalign{\smallskip}
%&=\sum↓{0≤i≤n+1}{(-y)↑i\over i!}+f↓{n+1}(x)\,.\cr}$$

Repeating,
$$V(c)=\left({h+2\over h}\right)↑t(h-t+1)↑{\bar{2}}-\left({h+1\over h}\right)↑t
(h-t+1)-\left({h+1\over h}\right)↑{2t}(h-t+1)↑2\,.$$
Because $V(c)$ is $O(t)$, we must not introduce any errors of approximation
unless their contribution is $o(t)$. Note that $\alpha$ and $e↑{\alpha}$ are
$O(1)$.
$$\eqalign{V(c)&\approx e↑{2\alpha}\left(1-{2t\over h↑2}\right)
(h-t+1)↑{\bar{2}}-e↑{\alpha}\left(1-{t\over 2h↑2}\right)(h-t)
-e↑{2\alpha}\left(1-{t\over h↑2}\right)(h-t+1)↑2\cr
\noalign{\smallskip}
&\approx e↑{2\alpha}(h-t+1)\left(\left(1-{2t\over h↑2}\right)(h-t+2)-
\left(1-{t\over h↑2}\right)(h-t+1)\right)-e↑{\alpha}(h-t)\cr
\noalign{\smallskip}
&=e↑{2\alpha}(h-t+1)\left(1+{t\over h↑2}(-2h+2t-4+h-t+1)\right)
-e↑{\alpha}(h-t)\cr
\noalign{\smallskip}
&\approx e↑{2\alpha}(h-t)\left(1+{t\over h↑2}(-h+t)\right)-e↑{\alpha}(h-t)\cr
\noalign{\smallskip}
&=e↑{2\alpha}\left((h-t)-{t(h-t)↑2\over h↑2}\right)-e↑{\alpha}(h-t)\cr
\noalign{\smallskip}
&=t\left({e↑{2\alpha}-e↑{\alpha}\over\alpha}(1-\alpha)-e↑{2\alpha}(1-\alpha)↑2
\right)=t\,g(\alpha)\,.\cr}$$
{}
$$\vcenter{\halign{$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\quad%
&$#$\hfil\quad&$#$\hfil\quad&$#$\hfil\cr
\alpha&0.2&0.4&0.6&0.7&0.8&0.9\cr
\noalign{\smallskip}
g(\alpha)&0.123&0.299&0.467&0.510&0.484&0.338\cr}}$$

We conclude that the movement of the cellar pointer is not costly in
practice (symbol tables are seldom even half full, so probably much
less than $t/3$ is a safe conjecture for the typical number of moves).
The standard deviation is never more than about $\sqrt{t/2}$, so
performance is very consistent.




\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
September 29, 1986.
%revised date;
%subsequently revised.

\bye
\proclaim Lemma. For $x>0${}
$$\left.\eqalign{1-x&\cr
1-x+x↑2-x↑3&\cr
\hbox{\rm etc.}&\cr}
\right\}<{1\over 1+x}<
\left\{\eqalign{&1\cr
&1-x+x↑2\cr
&1-x+x↑2-x↑3+x↑4\cr
&\hbox{\rm etc.}\cr}
\right.$$
as can be seen multiplying by $1+x$. Integrating, we get for $y>0$
$$\left.\eqalign{0&\cr
y-y↑2/2&\cr
y-y↑2/2+y↑3/3-y↑4/4&\cr
\hbox{\rm etc.}&\cr}
\right\}<
\int↓0↑y{1\over 1+x}\,dx=\ln(1+y)<
\left\{\eqalign{&y\cr
&y-y↑2/2+y↑3/3\cr
&\hbox{\rm etc.}\cr}
\right.$$
Together with $\ln\bigl((1+y)↑p\bigr)=p\ln(1+y)$, for positive~$p$
and~$y$, exponentiating gives
$$\left.\eqalign{1&\cr
\exp(px-px↑2/2)&\cr
\hbox{\rm etc.}&\cr}
\right\}<
(1+x)↑p<
\left\{\eqalign{&\exp(px)\cr
&\exp(px-px↑2/2+px↑3/3\cr
&\hbox{\rm etc.}\cr}
\right.$$
so we can say
$$(1+x)↑p=\exp(px)\cdot\exp(-px↑2/2)\cdot\exp(px↑3/3)\cdots\;.$$
Another useful inequality: because $e↑{-x}=1-\int↓{-x}↑0e↑{-y}\,dy$,
and $e↑{-y}>0$, for $x>0$ successive integrations give
$$e↑{-x}\left\{\eqalign{&<1\cr
&>1-x\cr
&<1-x+x↑2/2\cr
&>1-x+x↑2/2-x↑3/6\cr
&\quad\hbox{\rm etc.}\cr}
\right.$$

\bye